//最长的斐波那契子序列的长度（严格递增）
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        //如果单单以nums[i] 定义dp数组 我们无从知道这个斐波那契数列是什么
        //但只要有两个值作为参考 就可以将整个斐波那契数列找出来 所以需要二维dp
        //dp[i][j] 以arr[i] 和 arr[j]结尾的最长的斐波那契子序列的长度
		//这里采用的优化方式是 一开始就将全部的数据都用哈希存起来
		//因为他严格递增 所以只要出现重复的数 仅保存最新的即可
        int n=arr.size();
        int res=0;
        vector<vector<int>>dp(n,vector<int>(n,2));
        unordered_map<int,int>hash;
        for(int i=0;i<n;i++) hash[arr[i]]=i;
        for(int j=2;j<n;j++)
        {
            for(int i=1;i<j;i++)
            {
                auto it=hash.find(arr[j]-arr[i]);
                if(it!=hash.end() && it->second < i)
                {
                    int index=it->second;
                    dp[i][j]=dp[index][i]+1;
                    res=res<dp[i][j]?dp[i][j]:res;
                }
            }
        }
        return res;
    }
};
//最长等差数列（不严格递增）
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        //dp[i][j] 以nums[i] 和nums[j]结尾的最长等差数列的长度
        //所以需要我们在[0-i-1]这个区间 看2*nums[i]-nums[j]这个值是否存在
        //如果采用遍历的方式 那整体的时间复杂度就是O(N^3)
        //所以需要在找值这里进行优化
        //优化方式: 哈希
        //我们需要知道 待查找的值距离i下标最近的那个
        //因为带查找值可能有好几个下标 找最大的那个 能形成的等差数列也就长
        //  1 4 8(1) 6 7 8(2) 10
        //  6 7 8(1) 4 8(2) 12 14
        //如果我们确定j去找 i 和 k 
        //每次都要从头来遍历i
        //如果确定i去遍历j 那么我们只需要将i之前的值存入哈希表就可以解决了
        //找的一定是距离i最近的那个值
        int n=nums.size();
        vector<vector<int>>dp(n,vector<int>(n,2));
        unordered_map<int,int>hash;//->数值 下标
        hash[nums[0]]=0;
        int res=2;
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int a=2*nums[i]-nums[j];
                if(hash.find(a)!=hash.end())
                dp[i][j]=dp[hash[a]][i]+1;
                res=dp[i][j]>res?dp[i][j]:res;
            }
            hash[nums[i]]=i;
        }
        return res;
    }
};
